package de.parsemis.algorithms.dagpSpan;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

import de.parsemis.graph.HPGraph;
import de.parsemis.miner.environment.LocalEnvironment;
import de.parsemis.miner.general.Frequency;
import de.parsemis.miner.general.IntFrequency;

public class DFSCodePattern<NodeType, EdgeType> extends
		DFSCode<NodeType, EdgeType> {

	private ArrayList<DFSCode<NodeType, EdgeType>> instances;
	
	public DFSCodePattern(GThreadEnvironment<NodeType, EdgeType> tenv) {
		super(tenv);
		// TODO Auto-generated constructor stub
		instances = new ArrayList<DFSCode<NodeType, EdgeType>>();
	}

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	

	public void add(DFSCode<NodeType, EdgeType> code){
		instances.add(code);
	}
	

	public Iterator<DFSCode<NodeType, EdgeType>> getInstancesIterator(){
		return instances.iterator();
	}

	/** @return the frequency (finally) associated with this DFS-code */
	/**
	 * @author xujinghu
	 * FIXME: 模式的频繁度计算方法
	 * @return the frequency (finally) associated with this DFS-code Pattern
	 */
	public final Frequency frequency() {
		//LocalEnvironment<NodeType, EdgeType> env = LocalEnvironment.env(this);
/*		HashSet<Integer> hashSet=new HashSet<Integer>();
		
		for(DFSCode<NodeType, EdgeType> code: instances){
			hashSet.add(code.toHPFragment().graphIterator().next().getIndex());
		}
		
		IntFrequency count = new IntFrequency(hashSet.size());
		
		return count;*/
		return super.frequency();
	}
	
	public boolean isCanonical() {
		// create and initilize embedding Arrays
		final int nc = me.toHPGraph().getNodeCount();
		final int ec = me.toHPGraph().getEdgeCount();
		final GThreadEnvironment<NodeType, EdgeType> tenv = super.tenv();
		final int[] ackNodes = tenv.getIntArray(nc, UNUSED);
		final int[] usedNodes = tenv.getIntArray(nc, UNUSED);
		final int[] usedEdges = tenv.getIntArray(ec, UNUSED);
		final MinExtensionSet<NodeType, EdgeType> set = tenv.getExtensionSet();

		final boolean ret = isCan(set, ackNodes, usedNodes, usedEdges);

		// release Arrays
		tenv.push(set);
		tenv.push(ackNodes);
		tenv.push(usedNodes);
		tenv.push(usedEdges);
		return ret;
	}

	
	private boolean isCan(final MinExtensionSet<NodeType, EdgeType> set,
			final int[] ackNodes, final int[] usedNodes, final int[] usedEdges) {
		final LocalEnvironment<NodeType, EdgeType> env = LocalEnvironment.env(this);
		final HPGraph<NodeType, EdgeType> hp = me.toHPGraph();

		for (int edge = hp.getMaxEdgeIndex() - 1; edge >= 0; --edge) {
			if(!hp.isValidEdge(edge)){
				continue;
			}
			final int edgeLabelIndex = env.getEdgeLabelIndex(hp.getEdgeLabel(edge));
			int foundEdge = -2;
			GSpanEdge<NodeType, EdgeType> ack = first;
			final int node = hp.getNodeB(edge);
			
			if (ack.getNodeA() != ack.getNodeB()){	//不是自环
				if (hp.getEdge(ack.getNodeA(), ack.getNodeA()) != -1) {	//发现自环
					return false; // a smaller DFSCode is found
				}
				
				if (edgeLabelIndex < ack.getEdgeLabel()){	//发现比起始边更小的边
					return false;
				}
				
				if (edgeLabelIndex == ack.getEdgeLabel()){	//发现跟起始边相等的边，开始递归查找
					// only DFSCodes with  label smaller than this will be searched 
					// first edge will be detected by recursion
					usedNodes[hp.getNodeA(edge)] = 0;
					usedNodes[hp.getNodeB(edge)] = 1;
					ackNodes[0] = hp.getNodeA(edge);
					ackNodes[1] = hp.getNodeB(edge);
					usedEdges[edge] = 1;
					foundEdge = edge;
				}
				
				if (foundEdge > -2 && ack.next != null) {// node is a start node
					final MinExtension<NodeType, EdgeType> exts = getExtensions(1,
							hp, node, usedEdges, usedNodes);
					set.addAll(exts);
					// recursiv extension to find a smaller DFSCode
					if (!isCan2(ack.next, set, 1, usedNodes, usedEdges, ackNodes, hp)) {//FIXME：标准DFSCode检查
						// a smaller DFSCode is found
						set.removeAndFreeAll(exts);
						return false;
					}
					set.removeAndFreeAll(exts);
				}
				usedNodes[node] = -1;
				if (foundEdge > -1) {
					usedEdges[foundEdge] = UNUSED;
				}
				
			}else{
				 // self edge
				/*final int edge_circle = hp.getEdge(node, node);
				if (edge_circle != -1) {
					if (nodeLabelIndex < ack.getLabelA()) {
						return false; // a smaller DFSCode is found
					}
					if (nodeLabelIndex == ack.getLabelA()) {
						// only DFSCodes will searched which starts same as this
						final int edgeIndex = edge_circle;
						final int edgeLabelIndex = hp.getEdgeLabelIndex(edge_circle,
								env);
						if (edgeLabelIndex < ack.getEdgeLabel()) {
							return false; // a smaller DFSCode is found
						}
						if (edgeLabelIndex == ack.getEdgeLabel()) {
							// equal starting edge found
							usedNodes[node] = 0;
							ackNodes[0] = node;
							usedEdges[edgeIndex] = 1;
							foundEdge = edgeIndex;
							ack = ack.next;
						}
					}
				}*/
			}
		}
		// no smaller is found
		return true;
	}
	
	private boolean isCan2(final GSpanEdge<NodeType, EdgeType> ackEdge,
			final MinExtensionSet<NodeType, EdgeType> set, final int lastNode,
			final int[] usedNodes, final int[] usedEdges, final int[] ackNodes,
			final HPGraph<NodeType, EdgeType> graph) {
		final MinExtension<NodeType, EdgeType> first = set.forward;
		for (MinExtension<NodeType, EdgeType> ack = first; ack.compareTo(first) == 0; ack = ack.forward) {
			// for each extension that fits the first one

			// remove it from set
			final MinExtension<NodeType, EdgeType> next = set.unlink(ack);

			if (usedEdges[ack.gEdgei] != UNUSED) {
				// skip already used edges
				if (!isCan2(ackEdge, set, lastNode, usedNodes, usedEdges,
						ackNodes, graph)) {
					// smaller DFSCode found
					set.relink(ack, next);
					return false;
				}
			} else {
				if (ack.getNodeB() == UNUSED) { // forward edge
					final int tmp = ackEdge.compareTo(ack, lastNode + 1);
					if (tmp > 0) {
						// smaller DFSCode found
						set.relink(ack, next);
						return false;
					}
					if (ackEdge.next == null || tmp < 0) {
						// smaller DFSCode didn't found
						set.relink(ack, next);
						return true;
					}
					// compute extensions from the new node
					usedNodes[ack.gNodeBi] = lastNode + 1;
					ackNodes[lastNode + 1] = ack.gNodeBi;
					usedEdges[ack.gEdgei] = 1;
					final MinExtension<NodeType, EdgeType> exts = getExtensions(
							lastNode + 1, graph, ack.gNodeBi, usedEdges,
							usedNodes);
					set.addAll(exts);
					// recursiv search
					if (!isCan2(ackEdge.next, set, lastNode + 1, usedNodes,
							usedEdges, ackNodes, graph)) {
						// smaller DFSCode found
						set.removeAndFreeAll(exts);
						set.relink(ack, next);
						return false;
					}
					set.removeAndFreeAll(exts);
					usedNodes[ack.gNodeBi] = UNUSED;
					ackNodes[lastNode + 1] = UNUSED;
					usedEdges[ack.gEdgei] = UNUSED;
				} else { // backward edge
					final int tmp = ackEdge.compareTo(ack, ack.getNodeB());
					if (tmp > 0) {
						// smaller DFSCode found
						set.relink(ack, next);
						return false;
					}
					if (ackEdge.next == null || tmp < 0) {
						// smaller DFSCode found
						set.relink(ack, next);
						return true;
					}
					// mark edge as used
					usedEdges[ack.gEdgei] = 1;
					// recursiv search
					if (!isCan2(ackEdge.next, set, lastNode, usedNodes,
							usedEdges, ackNodes, graph)) {
						// smaller DFSCode found
						set.relink(ack, next);
						return false;
					}
					usedEdges[ack.gEdgei] = UNUSED;
				}
			}
			set.relink(ack, next);
		}
		return true;
	}
	
}
